//双指针算法

// 1.移动零
// class Solution {
// public:
//     void moveZeroes(vector<int>& nums) {
//         int left = 0, right = 0;
//         int n = nums.size();
//         while(right < n)
//         {
//             if(nums[right] != 0)
//             {
//                 swap(nums[left++], nums[right]);
//             }
//             right++;
//         }
//     }
// };

// 2.复写零
// class Solution {
// public:
//     void duplicateZeros(vector<int>& arr) {
//         //1.先找到最后一个复写的数
//         int n = arr.size();
//         int cur = 0, dest = 0;
//         for(;dest < n;cur++)
//         {
//             if(arr[cur] == 0) dest++;
//             dest++;
//         }

//         //2.回调
//         cur--;//此时arr[cur]是最后一个要复写的数
//         int end = dest;
//         dest = n-1;
//         if(end == n + 1)
//             //有一个0越界了
//             arr[dest--] = arr[cur--];

//         //3.从后往前模拟
//         while(cur >= 0)
//         {
//             if(arr[cur] == 0)
//             {
//                 arr[dest--] = arr[cur];
//             }
//             arr[dest--] = arr[cur--];
//         }
//     }
// };


// 202. 快乐数
// class Solution {
// public:
//     int replace(int n)
//     {
//         //将该数替换为它每个位置上的数字的平方和
//         int ret = 0;
//         while(n)
//         {
//             ret += pow(n%10, 2);
//             n /= 10;
//         }
//         return ret;
//     }
//     bool isHappy(int n) {
//         int slow = n, fast = replace(slow);
//         while(slow != fast)
//         {
//             slow = replace(slow);
//             fast = replace(replace(fast));
//         }
//         return slow == 1;
//     }
// };

// 两数之和
// class Solution {
// public:
//     vector<int> twoSum(vector<int>& price, int target) {
//         //双指针
//         int left = 0, right = price.size() - 1;
//         while(left != right)
//         {
//             if(price[left] + price[right] > target) 
//                 right--;

//             //a+b （a大b小）
//             //如果结果大于target，说明a加任何一个x(b<x<a,都比b大)都不满足，因此不用再考虑a
//             //如果结果小于target，说明b加任何一个x(b<x<a,都比a小)都不满足，因此不用再考虑b
            
//             else if(price[left] + price[right] < target)
//                 left++;
//             else
//                 break;
//         }
//         // vector<int> ret = {price[left], price[right]};
//         // return ret;
//         return {price[left], price[right]};
//     }
// };


// 三数之和
// class Solution {
// public:
//     vector<vector<int>> threeSum(vector<int>& nums) {
//         //先排序
//         sort(nums.begin(), nums.end());
//         //双指针，先锁定一个数，再找target
//         // set<vector<int>> s;
//         vector<vector<int>> vv;
//         for(int i = nums.size() - 1; i >= 2;)
//         {
//             int j = 0, k = i - 1;
//             while(j < k)
//             {
//                 if(nums[j] + nums[k] > -nums[i]) 
//                     k--;
//                 else if(nums[j] + nums[k] < -nums[i])
//                     j++;
//                 else //保存结果
//                 {
//                     vector<int> v = {nums[i], nums[j], nums[k]};
//                     //查重
//                     vv.push_back(v);
//                     //继续查找有无匹配的组合
//                     //去重，j/k跳过重复的元素
//                     int tmpj = nums[j];
//                     while(j<k && nums[j] == tmpj)
//                         j++;
                    
//                     int tmpk = nums[k];
//                     while(j<k && nums[k] == tmpk)
//                         k--;
//                 }
//             }

//             //i跳过重复元素
//             int tmpi = nums[i];
//             while(i >= 2 && nums[i] == tmpi)
//                 i--;
//         }
//         // for(auto& v:s)
//         // {
//         //     vv.push_back(v);
//         // }
//         return vv;
//     }
// };

// 四数之和
// optimize the leetcode code
// class Solution {
// public:
//     vector<vector<int>> fourSum(vector<int>& nums, int target) 
//     {
//         // 1.先排序
//         sort(nums.begin(), nums.end());

//         // 2.锁定一个数lockNum
//         vector<vector<int>> ret;
//         int n = nums.size();
//         for(int i = 0 ; i < n - 3 ; i++)
//         {
//             // 3.利用三数之和的思想，找到和为target-lockNum的三元组
//             // 去重
//             while(i < n - 3 && nums[i] == nums[i-1]) i++;
//             for(int j = i + 1 ; j < n - 2 ; j++)
//             {      
//                 //去重
//                 while(j < n - 2 && nums[j] == nums[j-1]) j++;
//                 int left = j+1, right = n-1;
//                 long aim = (long)target - nums[i] - nums[j];
//                 while(left < right)
//                 {
//                     if(nums[left] + nums[right] < aim)
//                         left++;
//                     else if(nums[left] + nums[right] > aim)
//                         right--;
//                     else
//                     {
//                         //找到了
//                         // (1).保存结果四元组
//                         ret.push_back({nums[i], nums[j], nums[left++], nums[right--]});
//                         // (2).去重
//                         while(left < right && nums[left] == nums[left-1]) left++;
//                         while(left < right && nums[right] == nums[right+1]) right--;
//                     }
//                 }
//             }
//         }

//         return ret;
//     }
// };